Maximum gap between successive elements [Tricky]¶
Time: O(N); Space: O(N); hard
Given an unsorted array, find the maximum difference between the successive elements in its sorted form.
Return 0 if the array contains less than 2 elements.
Example 1:
Input: nums = [3,6,9,1]
Output: 3
Explanation:
The sorted form of the array is [1,3,6,9], either (3,6) or (6,9) has the maximum difference 3.
Example 2:
Input: nums = [10]
Output: 0
Explanation:
The array contains less than 2 elements, therefore return 0.
Example 3:
Input: nums = [3, 1, 1, 1, 5, 5, 5, 5]
Output: 2
Notes:
You may assume all elements in the array are non-negative integers and fit in the 32-bit signed integer range.
Try to solve it in linear time/space.
1. Comparison Sorting [O(NLogN), O(1)]¶
Intuition
Do what the question says.
Algorithm
Sort the entire array. Then iterate over it to find the maximum gap between two successive elements.
[12]:
class Solution1(object):
"""
Time: O(NLogN).
Time taken to sort the array is O(NLogN) (average case).
Time taken for linear iteration through the array is of O(N) complexity.
Hence overall time complexity is O(NLogN).
Space: No extra space needed, other than the input array (since sorting can usually be done in-place).
"""
def maximumGap(self, nums):
"""
:type nums: List[int]
:rtype: int
Time: O(NlogN); Space: O(N)
"""
# check if array is empty or small sized
if len(nums) < 2:
return 0
# sort the array
nums.sort()
# pre = nums[0]
# max_gap = float("-inf")
# for i in nums:
# max_gap = max(max_gap, i - pre)
# pre = i
# return max_gap
maxGap = 0
for i in range(len(nums)-1):
maxGap = max(nums[i + 1] - nums[i], maxGap)
return maxGap
[13]:
s = Solution1()
nums = [3, 6, 9, 1]
assert s.maximumGap(nums) == 3
nums = [10]
assert s.maximumGap(nums) == 0
nums = [3, 1, 1, 1, 5, 5, 5, 5]
assert s.maximumGap(nums) == 2
2. Radix Sort [O(d?(n+k)) ? O(n), O(n + k) ? O(n)]¶
3. Buckets and The Pigeonhole Principle [O(n + b) ? O(n), O(2?b) ? O(b)]¶
Intuition
Sorting an entire array can be costly. At worst, it requires comparing each element with every other element. What if we didn’t need to compare all pairs of elements? That would be possible if we could somehow divide the elements into representative groups, or rather, buckets. Then we would only need to compare these buckets.
See: https://leetcode.com/problems/maximum-gap/solution/abs
[14]:
class Solution3(object):
"""
Backed sort
"""
def maximumGap(self, nums) -> int:
"""
:type nums: List[int]
:rtype: int
"""
if len(nums) < 2:
return 0
# Init bucket.
max_val, min_val = max(nums), min(nums)
gap = max(1, (max_val - min_val) // (len(nums) - 1))
bucket_size = (max_val - min_val) // gap + 1
bucket = [{'min':float("inf"), 'max':float("-inf")} for _ in range(bucket_size)]
# Find the bucket where the n should be put
for n in nums:
# min_val / max_val is in the first / last bucket
if n in (max_val, min_val):
continue
i = (n - min_val) // gap
bucket[i]['min'] = min(bucket[i]['min'], n)
bucket[i]['max'] = max(bucket[i]['max'], n)
# Count each bucket gap between the first and the last bucket.
max_gap, pre_bucket_max = 0, min_val
for i in range(bucket_size):
# Skip the bucket it empty
if bucket[i]['min'] == float("inf") and \
bucket[i]['max'] == float("-inf"):
continue
max_gap = max(max_gap, bucket[i]['min'] - pre_bucket_max)
pre_bucket_max = bucket[i]['max']
# Count the last bucket
max_gap = max(max_gap, max_val - pre_bucket_max)
return max_gap
[15]:
s = Solution3()
nums = [3, 6, 9, 1]
assert s.maximumGap(nums) == 3
nums = [10]
assert s.maximumGap(nums) == 0
nums = [3, 1, 1, 1, 5, 5, 5, 5]
assert s.maximumGap(nums) == 2